package backMind

import (
	"math"
)

var minDist = math.MaxInt64

// 回溯思想
// 迷宫最短路径问题，从（0，0）起始位置到(i,j)的最短路径
// i, j表示当前位置(纵横坐标)， w表示迷宫路径信息
// dist 最短路径
// i
// ^
// |
// | - - -> j

func MinDistBT(i, j, dist, n int, w [][]int) {

	// 已经到达n-1,n-1的位置了
	if i == n-1 && j == n-1 {
		// 累加结束位置节点
		dist += w[n-1][n-1]
		// 记录最小路径
		if dist < minDist {
			minDist = dist
		}
		return
	}

	// 往上走 更新i = i+1, j=j
	if i < n-1 {
		// dist 需要累加上当前位置的路径
		MinDistBT(i+1, j, dist+w[i][j], n, w)
	}

	// 往右走，更新i=i, j=j+1
	if j < n-1 {
		// dist 需要累加上当前位置的路径
		MinDistBT(i, j+1, dist+w[i][j], n, w)
	}

}
